﻿#define _CRT_SECURE_NO_WARNINGS 1

//class Solution {
//public:
//
//    int getMaxLen(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> f(n);
//        vector<int> g(n);
//        f[0] = nums[0] > 0 ? 1 : 0;
//        g[0] = nums[0] < 0 ? 1 : 0;
//
//        int maxlen = f[0];
//        for (int i = 1; i < n; i++)
//        {
//            if (nums[i] > 0)
//            {
//                f[i] = f[i - 1] + 1;
//                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
//            }
//            if (nums[i] < 0)
//            {
//                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
//                g[i] = f[i - 1] + 1;
//            }
//            maxlen = max(f[i], maxlen);
//        }
//        return maxlen;
//    }
//};

//class Solution {
//public:
//    int numberOfArithmeticSlices(vector<int>& nums) {
//        int count = 0;
//        int n = nums.size();
//        if (n < 3) return count;
//        for (int i = 2; i < n; i++)
//        {
//            int value = nums[i] - nums[i - 1];
//            for (int j = i - 1; j > 0; j--)
//            {
//                if (value == nums[j] - nums[j - 1]) count++;
//                else break;
//            }
//        }
//        return count;
//    }
//};

//class Solution {
//public:
//    int maxTurbulenceSize(vector<int>& arr) {
//        int n = arr.size();
//        vector<int> dp(n, 1);
//        if (n == 1) return 1;
//        if (n == 2) return arr[0] == arr[1] ? 1 : 2;
//        dp[1] = arr[0] == arr[1] ? 1 : 2;
//        int maxlen = dp[1];
//        for (int i = 2; i < n; i++)
//        {
//            if (arr[i - 2] > arr[i - 1] && arr[i - 1] < arr[i]
//                || arr[i - 2] < arr[i - 1] && arr[i - 1] > arr[i])
//            {
//                dp[i] = dp[i - 1] + 1;
//            }
//            else if (arr[i - 1] != arr[i])
//            {
//                dp[i] = 2;
//            }
//            maxlen = max(dp[i], maxlen);
//        }
//        return maxlen;
//    }
//};

//class Solution {
//public:
//    bool wordBreak(string s, vector<string>& wordDict) {
//        int n = s.size();
//        vector<bool> dp(n + 1);
//        dp[0] = true;
//        s = ' ' + s;
//        unordered_set<string> hash(wordDict.begin(), wordDict.end());
//        for (int i = 1; i <= n; i++)
//        {
//            int j = i;
//            while (j >= 1)
//            {
//                if (dp[j - 1] && hash.find(s.substr(j, i - j + 1)) != hash.end())
//                {
//                    dp[i] = true;
//                    break;
//                }
//                j--;
//            }
//            if (j == 0) dp[i] = false;
//        }
//        return dp[n];
//    }
//};

//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//
//int main()
//{
//    int N = 0;
//    int n = 0, m = 0;
//    vector<int> v;
//    cin >> N;
//    while (N)
//    {
//        int value = 0;
//        while (cin >> value)
//        {
//            v.push_back(value);
//        }
//    }
//    sort(v.begin(), v.end());
//
//    int value = v[0];
//    for (int i = 1; i < v.size(); i++)
//    {
//        if (value == v[i]) n = value;
//        if (value + 2 == v[i]) m = value + 1;
//        value = v[i];
//    }
//    cout << m << " " << n << endl;
//    return 0;
//}

//class Solution {
//public:
//    int findSubstringInWraproundString(string s) {
//        int n = s.size();
//        vector<int> slen(n, 1);
//        unordered_map<char, int> hash;
//        for (int i = 1; i < n; i++)
//        {
//            if (s[i - 1] + 1 == s[i] || s[i - 1] - 25 == s[i])
//            {
//                slen[i] += slen[i - 1];
//            }
//        }
//
//        for (int i = 0; i < n; i++)
//        {
//            hash[s[i]] = max(hash[s[i]], slen[i]);
//        }
//        int maxcount = 0;
//        for (auto& e : hash) maxcount += e.second;
//        return maxcount;
//    }
//};

//class Solution {
//public:
//    int findLength(vector<int>& nums1, vector<int>& nums2) {
//        int maxlen = 0, len = 0;
//        for (int i = 0; i < nums1.size(); i++)
//        {
//            for (int j = 0; j < nums2.size(); j++)
//            {
//                len = 0;
//                int stri = i, strj = j;
//                while (stri < nums1.size() && strj < nums2.size() && nums1[stri] == nums2[strj])
//                {
//                    len++;
//                    stri++;
//                    strj++;
//                }
//                maxlen = max(len, maxlen);
//            }
//        }
//        return maxlen;
//    }
//};

//class Solution {
//public:
//    int lengthOfLIS(vector<int>& nums) {
//        int n = nums.size();
//        int maxlen = 1;
//        vector<int> dp(n, 1);
//
//        for (int i = 1; i < n; i++)
//        {
//            for (int j = i - 1; j >= 0; j--)
//            {
//                if (nums[i] > nums[j])  dp[i] = max(dp[j] + 1, dp[i]);
//            }
//            maxlen = max(maxlen, dp[i]);
//        }
//        return maxlen;
//    }
//};

//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main()
//{
//	int n = 0;
//	vector<int> v;
//	cin >> n;
//	while (n--)
//	{
//		int value = 0;
//		cin >> value;
//		v.push_back(value);
//	}
//
//	int len = v.size();
//	int sum = 0;
//	if (len % 2 == 0)
//	{
//		for (int i = 1; i < len; i += 2)
//		{
//			sum += v[i - 1] * v[i];
//		}
//	}
//	else
//	{
//		for (int i = 1; i < n - 1; i += 2)
//		{
//			sum += v[i - 1] * v[i];
//		}
//		sum += v[len - 1];
//	}
//	cout << sum << endl;
//	return 0;
//}

//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main()
//{
//	int n = 0;
//	vector<int> v;
//	cin >> n;
//	while (n--)
//	{
//		int value = 0;
//		cin >> value;
//		v.push_back(value);
//	}
//
//	int sum = 0;
//	for (int i = 0; i < v.size(); i++)
//	{
//		for (int j = i + 1; j < v.size(); j++)
//		{
//			sum += v[i] * v[j];
//		}
//	}
//	cout << sum << endl;
//	return 0;
//}

//class Solution {
//public:
//    int wiggleMaxLength(vector<int>& nums) {
//        int n = nums.size();
//        if (n == 1) return 1;
//        if (n == 2) return nums[0] != nums[1] ? 2 : 1;
//        vector<int> dp(n, 1);
//        int ret = 1;
//        dp[1] = nums[0] != nums[1] ? 2 : 1;
//        for (int i = 2; i < n; i++)
//        {
//            int j = i - 1;
//            while (j > 0)
//            {
//                if (nums[j - 1] > nums[j] && nums[j] < nums[i])
//                {
//                    dp[i] = dp[j] + 1;
//                    break;
//                }
//                if (nums[j - 1] < nums[j] && nums[j] > nums[i])
//                {
//                    dp[i] = dp[j] + 1;
//                    break;
//                }
//                j--;
//            }
//            if (j == 0 && nums[i] != nums[0])
//            {
//                dp[i] = 2;
//            }
//            ret = max(dp[i], ret);
//        }
//        return ret;
//    }
//};